﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SevenAlgorithms.斐波那契查找
{
    internal class MainProject
    {
        public const int FIB_MAX_SIZE = 40;

        static void Main(string[] args)
        {
            int[] array = new int[] { -1, 0, 3, 5, 9, 12,45 };

            Console.WriteLine(FibFind(array, 9));
            Console.ReadKey();
        }

        public static int FibFind(int[] nums, int val)
        {
            int[] fibArray = new int[FIB_MAX_SIZE];

            Fibonaccii(fibArray);

            int k = 0;

            while (fibArray[k] < nums.Length - 1) k++;

            int size = fibArray[k] + 1;

            List<int> temp = new List<int>();
            temp.AddRange(nums);
            for (int i = nums.Length; i <= fibArray[k]; i++)
            {
                temp.Add(nums[nums.Length - 1]);
            }

            int[] tempArrat = temp.ToArray();

            int left = 0;
            int right = fibArray[k];

            while (left <= right)
            {
                int mid = left + fibArray[k - 1];
                if (tempArrat[mid] < val)
                {
                    left = mid + 1;
                    k -= 2;//因为是第二段，代表的是区间长度
                }
                else if (tempArrat[mid] > val)
                {

                    right = mid - 1;
                    k -= 1; ;//因为是第二段，代表的是区间长度
                }
                else
                {
                    if (mid < nums.Length)
                        return mid; //若相等则说明mid即为查找到的位置
                    else
                        return nums.Length - 1; //若mid>=n则说明是扩展的数值,返回n-1
                }
            }
            return -1;
        }

        public static void Fibonaccii(int[] array)
        {
            if (array == null) return;
            if (array.Length == 1) array[0] = 0;
            if (array.Length >= 2)
            {
                array[0] = 0;
                array[1] = 1;
            }
            for (int i = 2; i < array.Length; i++)
            {
                array[i] = array[i - 1] + array[i - 2];
            }
        }
    }
}
